﻿using System;
using System.Collections.Generic;

namespace SubsetSumS
{
    class SubsetSumS
    {
        struct Subsets //We will keep our information here for clarity
        {
            public readonly int Sum, ArrayIndex, SubsetIndex;

            public Subsets(int subsetSum, int arrayIndex, int subsetIndex)
            {
                Sum = subsetSum; // Contains our subset sum
                ArrayIndex = arrayIndex; // Contains the index in the main array
                SubsetIndex = subsetIndex; // Contains the index of the subset
            }
        }

        static void PrintResult(int[] array, params int[] indexes)
        {
            if (indexes.Length == 0)
            {
                Console.WriteLine("No");
            }
            else
            {
                Console.Write("Yes (");
                for (int index = indexes.Length - 1; index > 0; index--)
                {
                    Console.Write("{0} + ", array[indexes[index]]);
                }
                Console.WriteLine("{0})", array[indexes[0]]);
            }
        }
        /* Restores indices of our subset */
        static int[] FoundParentNumberIndexes(List<Subsets> subsetSums)
        {
            List<int> indexes = new List<int>();
            Subsets currentSubsetSum = subsetSums[subsetSums.Count - 1];
            indexes.Add(currentSubsetSum.ArrayIndex);
            int currentIndex = currentSubsetSum.SubsetIndex;

            while (currentIndex != -1)
            {
                currentSubsetSum = subsetSums[currentIndex];
                indexes.Add(currentSubsetSum.ArrayIndex);
                currentIndex = currentSubsetSum.SubsetIndex;
            }

            return indexes.ToArray();
        }

        static void FoundSubsetSum(int[] array, int sum)
        {
            List<Subsets> subsetSums = new List<Subsets>(1 << array.Length);
            subsetSums.Add(new Subsets( array[0], 0, -1 ));

            //If any of our numbers is the subset
            for (int index = 0, length = array.Length; index < length; index++)
            {
                if (array[index] == sum)
                {
                    PrintResult(array, index);
                    return;
                }
            }
            //We will find our solution of the problem based on our past calculation
            for (int index = 1, length = array.Length; index < length; index++)
            {
                for (int sumsIndex = 0, count = subsetSums.Count; sumsIndex < count; sumsIndex++)
                {
                    int currentSum = array[index] + subsetSums[sumsIndex].Sum;
                    subsetSums.Add(new Subsets(currentSum, index, sumsIndex));
                    if (currentSum == sum)
                    {
                        int[] sumIndexSequence = FoundParentNumberIndexes(subsetSums);
                        PrintResult(array, sumIndexSequence);
                        return;
                    }
                }
                subsetSums.Add(new Subsets(array[index], index, -1));
            }
            //If nothing is found
            PrintResult(array);
        }

        static void Main()
        {
            Console.Write("Please enter the length of your array: ");
            int arrayLength = int.Parse(Console.ReadLine());

            Console.Write("Enter an integer for S: ");
            int s = int.Parse(Console.ReadLine());

            int[] numbers = new int[arrayLength];
            for (int index = 0; index < arrayLength; index++)
            {
                Console.Write("Index [{0}]: ", index);
                numbers[index] = int.Parse(Console.ReadLine());
            }

            FoundSubsetSum(numbers, s);
        }
    }
}
